package org.hot100_1;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class leetcode81 {
//    public boolean wordBreak(String s, List<String> wordDict) {
//        Set<String> set = new HashSet<>(wordDict);
//
//        boolean [] dp = new boolean[s.length()+1];
//
//        dp[0]=true;
//
//        for (int i = 0; i <=s.length(); i++) {
//            for (String word:set) {
//                if (word.length()<=i && dp[i-word.length()] && word.equals(s.substring(i-word.length(),i))){
//                    dp[i]=true;
//                    break;
//                }
//            }
//        }
//
//        return dp[s.length()];
//    }

    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s. length();
        Set<String> set= new HashSet<>();
        for (String str:wordDict) {
            set.add(str);
        }
        boolean [] dp = new boolean[n+1];
        dp[0]=true;
        for (int i = 0; i <=n; i++) {
            for (String word:set) {
                if (word.length()<=i && dp[i-word.length()] && word.equals(s.substring(i-word.length(),i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        boolean [] dp = new boolean[3];

        for (boolean test:dp) {
            System.out.println(test);
        }

    }
}
